# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.count = 0
        self.search(root)
        return self.count

    def search(self, root: TreeNode):
        if root.left:
            self.count += 1
            self.search(root.left)
        self.count += 1
        if root.right:
            self.count += 1
            self.search(root.right)


class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.deepth, now_note, self.deepest_count = 0, root, 0
        while now_note.right:
            self.deepth += 1
            now_note = now_note.right
        try:
            self.search(root, 0)
        except:
            return 2 ** (self.deepth + 1) - 1 + self.deepest_count

    def search(self, root: TreeNode, deepth):
        if deepth > self.deepth:
            if root:
                self.deepest_count += 1
            else:
                raise StopAsyncIteration
        else:
            self.search(root.left, deepth + 1)
            self.search(root.right, deepth + 1)
